1. Field of the Invention
This invention relates to the use, with or without a network processor, of an Open Shortest Path First algorithm for the efficient routing of people or other objects in non-data networking applications
2. Discussion of Related Art
The internet world is composed of a series of routers that route packets of information between a starting point and a destination. The packets typically are routed through a number of intermediate points or nodes. The internet is intended to be self-healing so that, if a router at one node becomes unavailable to relay the packets, one or more alternate routes will be located and used. The unavailability could be a ‘soft’ failure due, for example, to a problem of loading the packets into the router due to a noisy communication link, or an overload or congestion of traffic through the node. Or it could be a ‘hard’ failure, caused by electrical outages, a breakdown of equipment, an internet virus, terrorist attack or other causes resulting in a malfunctioning or failure of hardware or software at the router node.
An internet program or algorithm called Open Shortest Path First (OSPF) is widely used to route internet traffic from its origin to its destination along the most efficient path available. The OSPF is an algorithm that monitors all links out of a given router location, and updates the statistics on each link, based on the amount of throughput that the link is handling at a given time or within a specific time frame. A weighted cost factor for using each link is determined based primarily on this throughput and, periodically, all routers in the system share this cost information. This enables the internet to determine the most logical pathway for routing packets over the internet. The algorithm thus builds tables for each router that describe all of the links from one particular router to another, and denote which particular link would be most advantageous at a particular instant. The advantage can be based on the dollar cost, the shortest length of time to complete the transfer, the best routing for transporting the particular type or priority of information being transmitted, the routing with the highest security, or any number of other parameters. The algorithm is continuously collecting information on each router, and is updating its own routing tables, which it then shares with other routers.
In addition to updating and exchanging information with other routers, the OSPF software uses an error reporting protocol commonly referred to as an ICMP or Internet Control Message Protocol. This protocol provides a means for routers that encounter an error condition to report that condition to the original source. In addition to its reporting function, the ICMP may suggest possible actions that can be taken to correct the problem. It does not implement these changes but, rather, leaves it up to the source router or other programs or systems within the network to implement the changes.
Every router includes such a common control point function running OSPF. The router may have many dozens of network processors (NPs), interfacing with the control point, whose principal function is the routing of packets of information. Optimum utilization of the NP mandates that it not become bogged down with time consuming activities that are peripheral to its main function, such as what to do with a packet if the intended destination is not in the routing table. Such a data packet is forwarded to the control point function in which the OSPF software is running. The OSPF will then determine how to reach the designation. In some instances, the control point processor is part of the network processor, possibly embedded in the same chip as the NP. In larger router installations, the OSPF functions could be distributed to specific control processors, or could be handled by a central CPU (central processing unit) running the entire OSPF software.
The class of routing problems in the real world is very large compared with the limited problem of routing in an IP network. Examples include: 1) the US air traffic control system (statically configured); 2) truck routing (best effort!); and 3) parcel delivery (fixed hub and spoke system). These systems generally are so huge, and hence complex, that there is no CPU that is cost effective enough to provide dynamic solutions to these problems. Others have devised routing systems for such uses as vehicle traffic, air flight management, track layouts and package transit and delivery. Some of these are discussed in the following patents.
U.S. Pat. No. 4,350,970 (1982) describes a motor vehicle routing system based on current stationary routing stations. The system transmits routing information and location data between stationary points and individual vehicles.
U.S. Pat. No. 4,760,530 (1988) describes a flight management system for aircraft that provides flight profile commands to an aircraft based on predicted flight costs.
U.S. Pat. No. 5,329,449 (1994) relates to a vehicle control system for a multi-branching track layout. The system stores and utilizes data concerning, for example, branch points and their addresses, length, direction and turning radii of branches, and vehicle running speeds.
U.S. Pat. No. 5,448,485 (1995) describes a system for specifying a route for, e.g., railroad or road network, or a fluid piping layout. The system facilitates the input of route information.
U.S. Pat. No. 5,831,860 (1998) relates to a system for redirecting a package while in transit. A two-way pager and a paging antenna are used to contact an addressee, a comparison is made between the actual location and the address specified by the sender, and disparities resolved.
None of these systems or programs uses the robust real time capabilities of a network processor and OSPF for non-data routing uses.